package com.zhulei.biji.suanfa.pace;

import java.util.Arrays;

/**
 * @description:
 * @author: zhulei
 * @create: 2025-03-11 10:48
 **/
public class latestTimeCatchTheBus {
    /**
     * 给你一个下标从 0 开始长度为 n 的整数数组 buses ，其中 buses[i] 表示第 i 辆公交车的出发时间。同时给你一个下标从 0 开始长度为 m 的整数数组 passengers ，其中 passengers[j] 表示第 j 位乘客的到达时间。所有公交车出发的时间互不相同，所有乘客到达的时间也互不相同。
     * <p>
     * 给你一个整数 capacity ，表示每辆公交车 最多 能容纳的乘客数目。
     * <p>
     * 每位乘客都会排队搭乘下一辆有座位的公交车。如果你在 y 时刻到达，公交在 x 时刻出发，满足 y <= x 且公交没有满，那么你可以搭乘这一辆公交。最早 到达的乘客优先上车。
     * <p>
     * 返回你可以搭乘公交车的最晚到达公交站时间。你 不能 跟别的乘客同时刻到达。
     * <p>
     * 注意：数组 buses 和 passengers 不一定是有序的。
     * <p>
     * 示例 1：
     * <p>
     * 输入：buses = [10,20], passengers = [2,17,18,19], capacity = 2
     * 输出：16
     * 解释：
     * 第 1 辆公交车载着第 1 位乘客。
     * 第 2 辆公交车载着你和第 2 位乘客。
     * 注意你不能跟其他乘客同一时间到达，所以你必须在第二位乘客之前到达。
     * 示例 2：
     * <p>
     * 输入：buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity = 2
     * 输出：20
     * 解释：
     * 第 1 辆公交车载着第 4 位乘客。
     * 第 2 辆公交车载着第 6 位和第 2 位乘客。
     * 第 3 辆公交车载着第 1 位乘客和你。
     * 提示：
     * <p>
     * n == buses.length
     * m == passengers.length
     * 1 <= n, m, capacity <= 105
     * 2 <= buses[i], passengers[i] <= 109
     * buses 中的元素 互不相同 。
     * passengers 中的元素 互不相同 。
     * Related Topics
     * 数组
     * 双指针
     * 二分查找
     * 排序
     * <p>
     * 👍 94
     * 👎 0
     */
    public static void main(String[] args) {
        int[] buses = {3};
        int[] passengers = {2, 4};
        int capacity = 2;
        System.out.println(latestTimeCatchTheBus(buses, passengers, capacity));
    }

    public static int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
        Arrays.sort(buses);
        Arrays.sort(passengers);
        int pos = 0;
        int space = 0;
        for (int arrive : buses) {
            space = capacity;
            while (space > 0 && pos < passengers.length && passengers[pos] <= arrive) {
                space--;
                pos++;
            }
        }
        pos--;
        int lastCatchTime = space > 0 ? buses[buses.length - 1] : passengers[pos];
        while (pos >= 0 && passengers[pos] == lastCatchTime) {
            pos--;
            lastCatchTime--;
        }
        return lastCatchTime;
    }


    // 快速排序的入口方法
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    // 递归实现快速排序
    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 找到分区点
            int partitionIndex = partition(arr, low, high);

            // 递归排序左半部分
            quickSort(arr, low, partitionIndex - 1);

            // 递归排序右半部分
            quickSort(arr, partitionIndex + 1, high);
        }
    }

    // 分区函数
    private static int partition(int[] arr, int low, int high) {
        // 选择基准元素（这里选择最后一个元素作为基准）
        int pivot = arr[high];
        int i = low - 1; // i是小于基准元素的最后一个位置

        for (int j = low; j < high; j++) {
            // 如果当前元素小于或等于基准元素
            if (arr[j] <= pivot) {
                i++;
                // 交换arr[i]和arr[j]
                swap(arr, i, j);
            }
        }

        // 将基准元素放到正确的位置
        swap(arr, i + 1, high);

        // 返回分区点的索引
        return i + 1;
    }

    // 交换数组中两个元素的位置
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
